Benders Decomposition for the Design of a Hub and Shuttle Public Transit System

摘要

The BusPlus project aims at improving the off-peak hours public transitservice in Canberra, Australia. To address the difficulty of covering a largegeographic area, BusPlus proposes a hub and shuttle model consisting of acombination of a few high-frequency bus routes between key hubs and a largenumber of shuttles that bring passengers from their origin to the closest huband take them from their last bus stop to their destination. This paper focuseson the design of bus network and proposes an efficient solving method to thismultimodal network design problem based on the Benders decomposition method.Starting from a MIP formulation of the problem, the paper presents a Bendersdecomposition approach using dedicated solution techniques for solvingindependent sub-problems, Pareto optimal cuts, cut bundling, and core pointupdate. Computational results on real-world data from Canberra's public transitsystem justify the design choices and show that the approach outperforms theMIP formulation by two orders of magnitude. Moreover, the results show that thehub and shuttle model may decrease transit time by a factor of 2, while stayingwithin the costs of the existing transit system.